#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>


using namespace std;

//class Solution {
//public:
//    // 字符串相加
//    string addStrings(string& num1, string& num2) {
//        int begin1 = 0, end1 = num1.size() - 1;
//        int begin2 = 0, end2 = num2.size() - 1;
//        int next = 0;
//        string ret;
//        ret.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);
//        while (begin1 <= end1 || begin2 <= end2) {
//            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
//            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
//            int res = val1 + val2 + next;
//            next = res / 10;
//            res = res % 10;
//
//            ret.push_back(res + '0');
//            end1--;
//            end2--;
//        }
//        if (next == 1)
//            ret.push_back('1');
//        std::reverse(ret.begin(), ret.end());
//        return ret;
//    }
//
//    // 一个字符乘上一个字符串
//    string Mul(char& ch, string& s) {
//        int end = s.size() - 1;
//        int bit = ch - '0';
//        int next = 0;
//        string ret;
//        ret.reserve(s.size() + 1);
//        while (end >= 0) {
//            int val = s[end] - '0';
//            int res = val * bit + next;
//            next = res / 10;
//            res %= 10;
//
//            ret += (res + '0');
//            end--;
//        }
//        if (next > 0)
//            ret += (next + '0');
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//
//    string multiply(string num1, string num2) {
//        // 将字符串拆分，然后分别进行乘，最后相加
//        // 先拆分,num1_a 为拆分的数组
//        int len = num1.size();
//        string num1_a[num1.size()];
//        for (int i = num1.size(); i > 0; i++) {
//            num1_a[i] += num1[i];
//            for (int j = 1; j < i; j++) {
//                num1_a[i] += '0';
//            }
//        }
//        // 将 num1_a 中的元素分别与 num2 相乘,结果放入新的数组中
//        string res[num1.size()];
//        for (int i = 0; i < num1.size(); i++) {
//            for (int j = 0; j < num1_a[i].size(); j++) {
//                if (num1_a[i][j] == '0')
//                    res[i] += num1_a[i][j];
//                else
//                    res[i] = Mul(num1_a[i][j], num2);
//            }
//        }
//        // 将所有的数加起来
//        string ret = "0";
//        for (int i = 0; i < num1.size(); i++)
//            ret = addStrings(ret, res[i]);
//        return ret;
//    }
//
//};

//class Solution {
//public:
//    string reverseStr(string s, int k) {
//        int len = s.size();
//
//        // 进行循环
//        int count = 0;
//        int num = 0;
//        int flag = 0;
//        for (int i = 1; i <= len; i++) {
//            // 进行计数，每一次到达 2k 次，我们开始反转
//            count = (count + 1) % (2 * k + 1);
//            // 反转前 k 个元素
//            if (count == 2 * k) {
//                reverse(s.begin() + num * k, s.begin() + (num + 1) * k);
//                num++;
//                flag = 1;
//            }
//        }
//        if (count < k)
//            reverse(s.end() - count, s.end());
//        if (count < 2 * k && count >= k && flag == 1)
//            reverse(s.end() - count - 1, s.end() - count + k - 1);
//        if (count < 2 * k && count >= k)
//            reverse(s.end() - count, s.end() - count + k);
//
//        return s;
//    }
//};

//class Solution {
//public:
//    string reverseStr(string s, int k) {
//        int len = s.size();
//
//        // 进行循环
//        int count = 0;
//        int num = 0;
//        int flag = 0;
//        for (int i = 1; i <= len; i++) {
//            // 进行计数，每一次到达 2k 次，我们开始反转
//            count = (count + 1) % (2 * k + 1);
//            // 反转前 k 个元素
//            if (count == 2 * k) {
//                reverse(s.begin() + num * k, s.begin() + (num + 1) * k);
//                num++;
//                flag = 1;
//            }
//        }
//        if (count < k)
//            reverse(s.end() - count - 1, s.end());
//        if (count < 2 * k && count >= k && flag == 1)
//            reverse(s.end() - count - 1, s.end() - count + k - 1);
//        if (count < 2 * k && count >= k)
//            reverse(s.end() - count, s.end() - count + k);
//
//        return s;
//    }
//};

//class Solution {
//public:
//    string reverseWords(string s) {
//        // 找到空格，然后交换
//        int pos1 = 0;
//        int pos2 = s.find(" ");
//        while (pos1 != std::string::npos) {
//            if(pos2 != std::string::npos)
//                reverse(s.begin() + pos1 + 1, s.begin() + pos2);
//            else
//                reverse(s.begin() + pos1, s.end());
//            pos1 = pos2;
//            pos2 = s.find(' ', pos2 + 1);
//        }
//        return s;
//    }
//};

#include <vector>
class Solution {
public:
    // 字符串相加
    string addStrings(string& num1, string& num2) {
        int begin1 = 0, end1 = num1.size() - 1;
        int begin2 = 0, end2 = num2.size() - 1;
        int next = 0;
        string ret;
        ret.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);
        while (begin1 <= end1 || begin2 <= end2) {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int res = val1 + val2 + next;
            next = res / 10;
            res = res % 10;

            ret.push_back(res + '0');
            end1--;
            end2--;
        }
        if (next == 1)
            ret.push_back('1');
        reverse(ret.begin(), ret.end());
        return ret;
    }

    // 一个字符乘上一个字符串
    string Mul(char& ch, string& s) {
        int end = s.size() - 1;
        int bit = ch - '0';
        int next = 0;
        string ret;
        ret.reserve(s.size() + 1);
        while (end >= 0) {
            int val = s[end] - '0';
            int res = val * bit + next;
            next = res / 10;
            res %= 10;

            ret += (res + '0');
            end--;
        }
        if (next > 0)
            ret += (next + '0');
        reverse(ret.begin(), ret.end());
        return ret;
    }

    string multiply(string num1, string num2) {
        // 将字符串拆分，然后分别进行乘，最后相加
        // 先拆分,num1_a 为拆分的数组
        // 拆反了
        string* num1_a = new string[num1.size()];
        for (int i = 0; i < num1.size(); i++) {
            string tmp;
            tmp += num1[i];

            for (int j = 1; j < num1.size() - i; j++) {
                tmp += '0';
            }
            num1_a[i] = tmp;
        }
        // 将 num1_a 中的元素分别与 num2 相乘,结果放入新的数组中
        string* res = new string[num1.size()];

        for (int i = 0; i < num1.size(); i++) {
            for (int j = 0; j < num1_a[i].size(); j++) {
                if (num1_a[i][j] == '0')
                    res[i] += num1_a[i][j];
                else
                    res[i] = Mul(num1_a[i][j], num2);
            }
        }
        // 将所有的数加起来
        string ret = "0";
        for (int i = 0; i < num1.size(); i++)
            ret = addStrings(ret, res[i]);
        return ret;
    }
};

int main() {
    Solution s;
    s.multiply("123", "456");
    return 0;
}